/**
 * [198] 打家劫舍
 *
 * @format
 * @lc app=leetcode.cn id=198 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
// 动态规划（官方）
// 设对 nums[n] 的房屋列表进行偷窃，总计最高金额为：M(n)
//
// # 偷窃第 k 间房屋：      Mt(k) = M[k-2] + nums[k]
// # 不偷窃第 k 间房屋：    Mf(k) = M[k-1]
//
// # 状态转移方程（递推式）：M(n) = max{ Mt(k), mf(k) } => dp[i] = max(dp[i−2] + nums[i], dp[i−1])
//
// # 边界条件（首项）：
//                         dp[0] = nums[0]
//                         dp[1] = max(nums[0], nums[1])
var rob = function (nums) {
  const N = nums.length
  if (N <= 2) return Math.max(...nums)
  let i = 2
  const dp = [nums[0], Math.max(nums[0], nums[1])]
  while (i < N) dp[i] = Math.max(dp[i - 2] + nums[i], dp[i++ - 1])
  return dp[N - 1]
}
// 测试用例
// const nums = [6,3,10,8,2,10,3,5,10,5,3]
// const answer = 39
// console.log(rob(nums))
// @lc code=end

// 动态规划
/* var rob = function (nums) {
    let i = nums.length - 1
    const stack = [{ rob: nums[i--], notRob: 0 }]
    let top = null
    while (i >= 0) {
        top = stack[stack.length - 1]
        const newTop = {
            rob: nums[i] + top["notRob"],
            notRob: Math.max(top["rob"], top["notRob"])
        }
        stack.push(newTop)
        i--
    }
    top = stack[stack.length - 1]
    return Math.max(top["rob"], top["notRob"])
} */

// hashMap + 剪枝
/* var rob = function (nums) {
    const N = nums.length
    const map = { "l1-false": 0, "l1-true": nums[N - 1] }

    function shoudRob(index, isRobbed, cutOff) {
        const layer = N - index
        let key = ""
        if (isRobbed) {
            key = `l${layer}-false`
            if (map[key] === undefined) map[key] = shoudRob(index + 1, false, false)
        } else if (cutOff) {
            key = `l${layer}-true`
            if (map[key] === undefined) map[key] = nums[index] + shoudRob(index + 1, true, false)
        } else {
            let key1 = `l${layer}-true`
            let key0 = `l${layer}-false`
            if (map[key0] === undefined) map[key0] = shoudRob(index + 1, false, true)
            if (map[key1] === undefined) map[key1] = nums[index] + shoudRob(index + 1, true, false)
            map[key0] > map[key1] ? (key = key0) : (key = key1)
        }
        return map[key]
    }

    return shoudRob(0, false, false)
} */

// hashMap
/* var rob = function (nums) {
    const N = nums.length
    const map = { "l1-false": 0, "l1-true": nums[N - 1] }

    function shoudRob(index, isRobbed) {
        const layer = N - index
        let key = ""
        if (isRobbed) {
            key = `l${layer}-false`
            if (map[key] === undefined) map[key] = shoudRob(index + 1, false)
        } else {
            let key1 = `l${layer}-true`
            let key0 = `l${layer}-false`
            if (map[key0] === undefined) map[key0] = shoudRob(index + 1, false)
            if (map[key1] === undefined) map[key1] = nums[index] + shoudRob(index + 1, true)
            map[key0] > map[key1] ? (key = key0) : (key = key1)
        }
        return map[key]
    }

    return shoudRob(0, false)
} */
// Accepted
// 70/70 cases passed (55 ms)
// Your runtime beats 66.95 % of javascript submissions
// Your memory usage beats 5.95 % of javascript submissions (49.4 MB)

// 递归剪枝（超时）
/* var rob = function (nums) {
    const N = nums.length
    function shoudRob(index, isRobbed, cutOff) {
        if (index === N - 1) return isRobbed ? 0 : nums[N - 1]
        if (isRobbed) return shoudRob(index + 1, false, false)
        else if (cutOff) return nums[index] + shoudRob(index + 1, true, false)
        else {
            const robIt = nums[index] + shoudRob(index + 1, true, false)
            const doNotRob = shoudRob(index + 1, false, true)
            return Math.max(doNotRob, robIt)
        }
    }
    return shoudRob(0, false, false)
} */

// 暴力递归（超时）
/* var rob = function (nums) {
    const N = nums.length
    function shoudRob(index, isRobbed) {
        if (index === N - 1) return isRobbed ? 0 : nums[N - 1]
        if (isRobbed) return shoudRob(index + 1, false)
        else {
            const robIt = nums[index] + shoudRob(index + 1, true)
            const doNotRob = shoudRob(index + 1, false)
            return Math.max(doNotRob, robIt)
        }
    }
    return shoudRob(0, false)
} */
